package de.uni_potsdam.hpi.bpt.ai.util;

import java.util.ArrayList;
import java.util.List;

import de.uni_potsdam.hpi.bpt.ai.diagram.Edge;
import de.uni_potsdam.hpi.bpt.ai.diagram.Node;
import de.uni_potsdam.hpi.bpt.ai.diagram.Shape;

public class TransitiveClosure {
	
	protected boolean[][] matrix = null;
	protected List<Node> nodes;
	
	public TransitiveClosure(Shape diagram) {
		
		this.nodes = this.getNodes(diagram);
		this.calculateMatrix(this.getEdges(diagram));
	}
	
	/**
	 * Extracts all edges from a the childshapes of a shape
	 * 
	 * @param shape
	 * @return
	 */
	protected List<Edge> getEdges(Shape shape) {
		List<Edge> edges = new ArrayList<Edge>();
		
		for(Shape child : shape.getChildShapes()) {
			if (child instanceof Edge && BpmMetrics.isControlFlowArc(child)) {
				edges.add((Edge)child);
			}
			
			edges.addAll(getEdges(child));
		}
		return edges;
	}
	
	/**
	 * Extracts all edges from a the childshapes of a shape
	 * 
	 * @param shape
	 * @return
	 */
	protected List<Node> getNodes(Shape shape) {
		List<Node> nodes = new ArrayList<Node>();
		
		for(Shape child : shape.getChildShapes()) {
			if (child instanceof Node && BpmMetrics.isControlFlowNode(child)) {
				nodes.add((Node)child);
			}
			
			nodes.addAll(getNodes(child));
		}
		return nodes;
	}

	/**
	 * Calculates the transitive flow matrix for given nodes and edges
	 *  
	 * @param edges
	 */
	protected void calculateMatrix(List<Edge> edges) {
		
		// set up the matrix
		this.matrix = new boolean[this.nodes.size()][this.nodes.size()];
		
		for (Edge edge : edges) {
			int src = -1;
			int tgt = -1;
			
			for (Shape in : edge.getIncomings()) {
				if (in instanceof Node && BpmMetrics.isControlFlowNode(in)) {
					src = this.nodes.indexOf(in);
				}
			}

			for (Shape out : edge.getOutgoings()) {
				if (out instanceof Node && BpmMetrics.isControlFlowNode(out)) {
					tgt = this.nodes.indexOf(out);
				}
			}

			if (src > 0 && tgt > 0) {
				matrix[src][tgt] = true;
			}

		}
		
		/*
		 * Compute the transitive closure
		 */
		for (int i = 0; i < matrix.length; i++) 
			for (int j = 0; j < matrix.length; j++) 
				if (matrix[j][i])
					for (int k = 0; k < matrix.length; k++)
						matrix[j][k] = matrix[j][k] | matrix[i][k];
	}
	
	/**
	 * Check if there exists a directed path between two vertices
	 * @param v1 Vertex
	 * @param v2 Vertex
	 * @return <code>true</code> if there is a directed path from v1 to v2, <code>false</code> otherwise 
	 */
	public boolean hasPath(Node node1, Node node2) {
		int i = this.nodes.indexOf(node1);
		int j = this.nodes.indexOf(node2);
		return matrix[i][j];
	}
	
	/**
	 * Check if vertex is part of a loop
	 * @param v Vertex
	 * @return <code>true</code> if vertex is part of a loop, <code>false</code> otherwise
	 */
	public boolean isInLoop(Node node) {
		int index = this.nodes.indexOf(node);
		if (-1 == index) {
			return false;
		}
		
		return matrix[index][index];
	}
	
	/**
	 * Checks whether any node exists that is part of a loop
	 * @return <code>true</code> if diagram contains at least one loop
	 */
	public boolean hasLoops() {
		for (Node node : this.nodes) {
			if (this.isInLoop(node)) {
				return true;
			}
		}
		return false;
	}
}



